Back-and-forth method Totally Explained

Everything about Back-and-forth Method totally explained

In mathematical logic, especially set theory and model theory, the back-and-forth method is a method for showing isomorphism between countably infinite structures satisfying specified conditions. In particular:

It can be used to prove that any two countably infinite densely ordered sets (for example, linearly ordered in such a way that between any two members there's another) without endpoints are isomorphic. An isomorphism between linear orders is simply a strictly increasing bijection. This result implies, for example, that there exists a strictly increasing bijection between the set of all rational numbers and the set of all real algebraic numbers.

It can be used to prove that any two countably infinite atomless Boolean algebras are isomorphic to each other.

It can be used to prove that any two equivalent countable atomic models of a theory are isomorphic.

Application to densely ordered sets

Suppose that

(A, ≤_A) and (B, ≤_B) are linearly ordered sets;

They are both unbounded, in other words neither A nor B has either a maximum or a minimum;

They are densely ordered, for example between any two members there's another;

They are countably infinite. Fix enumerations (without repetition) of the underlying sets:
ť A = .
Now we construct a one-to-one correspondence between A and B that's strictly increasing. Initially no member of A is paired with any member of B. ť (1) Let i be the smallest index such that a_i isn't yet paired with any member of B. Let j be some index such that b_j isn't yet paired with any member of A and a_i can be paired with b_j consistently with the requirement that the pairing be strictly increasing. Pair a_i with b_j.

ť (2) Let j be the smallest index such that b_j isn't yet paired with any member of A. Let i be some index such that a_i isn't yet paired with any member of B and b_j can be paired with a_i consistently with the requirement that the pairing be strictly increasing. Pair b_j with a_i.

ť (3) Go back to step (1).

It still has to be checked that the choice required in step (1) and (2) can actually be made in accordance to the requirements. Using step (1) as an example:
If there are already a_p and a_q in A corresponding to b_p and b_q in B respectively such that a_p < a_i < a_q and b_p < b_q, we choose b_j in between b_p and b_q using density. Otherwise, we choose a suitable large or small element of B using the fact that B has neither a maximum nor a minimum. Choices made in step (2) are dually possible. Finally, the construction ends after countably many steps because A and B are countably infinite. Note that we'd to use all the prerequisites.
If we iterated only step (1), rather than going back and forth, then in some cases the resulting function from A to B would fail to be surjective. In the easy case of unbounded dense totally ordered sets it's possible to avoid step 2 by choosing the element b_j more carefully (by choosing j as small as possible), but this doesn't work for more complicated examples such as atomless Boolean algebras where steps 1 and 2 are both needed.

History

According to Hodges (1993): ť Back-and-forth methods are often ascribed to Cantor, Bertrand Russell and C. H. Langford […], but there's no evidence to support any of these attributions.

While the theorem on countable densely ordered sets is due to Cantor (1895), the back-and-forth method with which it's now proved was developed by Huntington (1904) and Hausdorff (1914). Later it was applied in other situations, most notably by Roland Fraïssé in model theory.

Further Information

Get more info on 'Back-and-forth Method'.

External Link Exchanges

Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:

<a href="http://back-and-forth_method.totallyexplained.com">Back-and-forth method Totally Explained</a>

Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned.